/**
 *  @file    GetCommonElements.c
 *  @brief   获取两个递增有序单链表的公共元素，并构造新链表返回
 *  @details 要求：
 *           - 输入链表为**带头结点**的递增单链表
 *           - 输出链表也应带头结点
 *           - **不破坏原链表结构**
 *           - 公共元素只保留一份（不去重）
 *           - 空链表或无交集 → 返回空链表（仅含头结点）
 *           - 时间复杂度 O(n + m)，空间复杂度 O(k)
 *  @author  WangBlue (wangjiping596@gmail.com)
 *  @date    2025‑07‑17 14:35
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// ------------------------- 链表结构定义 -------------------------

/**
 * @brief 单链表结点
 */
typedef struct node {
    int data;              ///< 数据域
    struct node *next;     ///< 指针域
} node, *link;

// ------------------------- 基本链表操作 -------------------------

/**
 * @brief 创建一个新数据结点（非头结点）
 * @param value 要存储的值
 * @return 成功返回指针，失败返回 NULL
 */
link createNode(int value) {
    link node = (link)malloc(sizeof(node));
    if (!node) return NULL;
    node->data = value;
    node->next = NULL;
    return node;
}

/**
 * @brief 初始化一个带头结点的链表
 * @param head 指向头指针的指针
 */
void initNode(link *head) {
    link node = (link)malloc(sizeof(node));
    if (!node) return;
    node->data = 0;       // 头结点 data 可忽略
    node->next = NULL;
    *head = node;
}

/**
 * @brief 头插法插入结点（数据域）
 * @param head 链表头指针（必须存在）
 * @param value 插入的值
 */
void insertHead(link head, int value) {
    if (!head) return;
    link node = createNode(value);
    if (!node) return;
    node->next = head->next;
    head->next = node;
}

/**
 * @brief 尾插法插入数据结点
 * @param head 带头结点的链表头指针
 * @param value 要插入的数据值
 */
void insertTail(link head, int value) {
    if (!head) return;
    link node = createNode(value);
    if (!node) return;

    link cur = head;
    while (cur->next) {
        cur = cur->next;
    }
    cur->next = node;
}

/**
 * @brief 打印链表中的所有数据结点（跳过头结点）
 * @param head 链表头指针
 */
void printList(link head) {
    if (!head || !head->next) return;
    for (link cur = head->next; cur; cur = cur->next) {
        printf("value is %d\n", cur->data);
    }
    printf("\n");
}

/**
 * @brief 释放整个链表（含头结点）
 * @param head 指向链表头指针的指针
 */
void destroy(link *head) {
    if (!head || !*head) return;
    link cur = *head;
    while (cur) {
        link temp = cur->next;
        free(cur);
        cur = temp;
    }
    *head = NULL;
    printf("SUCCESS\n");
}

// ------------------------- 核心函数：找公共元素 -------------------------

/**
 * @brief 获取两个有序单链表中的公共元素，构造新链表返回
 * @note  原链表不被修改，输出链表带头结点
 * @param l1 带头结点链表1
 * @param l2 带头结点链表2
 * @return 返回一个新链表（带头结点）包含所有交集元素
 */
link getCommonEles(link l1, link l2) {
    if (!l1 || !l1->next || !l2 || !l2->next) return NULL;

    link result = NULL;
    initNode(&result);         // 初始化结果链表（带头）

    link re = result;          // 尾插法构造结果链表

    link pa = l1->next;        // 跳过头结点
    link pb = l2->next;

    while (pa && pb) {
        if (pa->data < pb->data) {
            pa = pa->next;
        } else if (pa->data > pb->data) {
            pb = pb->next;
        } else {
            link node = createNode(pa->data);
            if (!node) {
                destroy(&result);
                return NULL;
            }
            re->next = node;
            re = node;
            pa = pa->next;
            pb = pb->next;
        }
    }

    return result;
}

// ------------------------- 主函数测试 -------------------------

int main() {
    link head1 = NULL;
    initNode(&head1);
    insertTail(head1, 1);
    insertTail(head1, 2);
    insertTail(head1, 3);

    link head2 = NULL;
    initNode(&head2);
    insertTail(head2, 2);
    insertTail(head2, 3);
    insertTail(head2, 4);

    link result = getCommonEles(head1, head2);
    if (result) {
        printList(result);  // 应输出 2 和 3
        destroy(&result);
    }

    return 0;
}
